package com.my.collection.queue.v2;

import sun.misc.Contended;

import java.util.concurrent.locks.ReentrantLock;

/**
 * Created by ZhongGang
 * at 2018/9/3 15:06
 * <p>
 * 初始头节点与尾节点均为元素数据为空的节点，
 * 头节点与尾节点之间的结点为真正的数据节点
 */
public class Queue<E> {
    @Contended
    private Node<E> head;//头结点，从头节点开始出队操作
    @Contended
    private Node<E> tail;//尾结点，从尾节点开始入队操作

    private ReentrantLock lock = new ReentrantLock();

    public Queue() {
        Node<E> head = new Node<>(null, null, null);
        Node<E> tail = new Node<>(null, null, null);
        this.head = head;
        this.tail = tail;
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    /**
     * 入队操作
     *
     * @param e
     */
    public void enqueue(E e) {
        try {
            this.lock.lock();

            Node<E> node = new Node<>(e, null, null);
            this.tail.prev.next = node;
            node.next = this.tail;
            node.prev = this.tail.prev;
            this.tail.prev = node;
        } finally {
            this.lock.unlock();
        }
    }

    /**
     * 出队操作
     *
     * @return
     */
    public E dequeue() {
        try {
            this.lock.lock();

            Node<E> node = this.head.next;
            if (node.equals(this.tail)) {
                return null;
            }

            E e = node.e;
            this.head.next = node.next;
            node.next.prev = this.head;
            return e;
        } finally {
            this.lock.unlock();
        }
    }

    /**
     * 队列长度
     *
     * @return
     */
    public int size() {
        int size = 0;
        for (Node<E> node = this.head.next; !node.equals(this.tail); node = node.next) {
            size += 1;
        }
        return size;
    }

    private static class Node<E> {
        private E e;//队列节点数据
        private Node<E> prev;//前节点
        private Node<E> next;//后节点

        Node(E e, Node<E> prev, Node<E> next) {
            this.e = e;
            this.prev = prev;
            this.next = next;
        }
    }

    public static void main(String[] args) throws Exception {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.size());

        Integer dequeue = queue.dequeue();
        System.out.println(dequeue);
        dequeue = queue.dequeue();
        System.out.println(dequeue);
        dequeue = queue.dequeue();
        System.out.println(dequeue);
        System.out.println(queue);
    }

}
